/*******************************************************************************
 * @file      lwheap.c
 * @brief     轻量级动态内存管理
 *
 * @history   V0.01, 2018-11-03, xiaoguolin, first implementation.
*******************************************************************************/
#include "lwheap.h"


#define __LWHEAP_ALLOCATED_MASK           0x00000001ul

#define __LWHEAP_BLOCK(block)             ((LwHeap_Block_t*)(block))

#define __LWHEAP_BLOCK_TO_UBPTR(block)    ((void*)(&(block)->next))
#define __LWHEAP_UBPTR_TO_BLOCK(ubptr)    (__LWHEAP_BLOCK(((uint32_t)(ubptr))-(sizeof(LwHeap_Block_t)-sizeof(LwHeap_Block_t*))))


void LwHeap_Init(LwHeap_t* heap)
{
    if(heap == NULL){
        return ;
    }

    heap->freeBlockListHeader.next = NULL;
    heap->freeBlockListHeader.size = 0;
#if LWHEAP_ENABLE_MEMEORY_USE_RECORD != 0
    heap->memCount.total = 0;
    heap->memCount.free = 0;
    heap->memCount.minval = 0;
#endif
#if LWHEAP_MEMORY_TRACE_LEVEL != 0
#if LWHEAP_USER_TRACE_DATA_TYPE == 0
    heap->freeBlockListHeader.__data = NULL;
    heap->freeBlockListHeader.__dlen = 0;
    heap->usedBlockListHeader.__data = NULL;
    heap->usedBlockListHeader.__dlen = 0;
#elif LWHEAP_USER_TRACE_DATA_TYPE == 1
    heap->freeBlockListHeader.__ustr = NULL;
    heap->usedBlockListHeader.__ustr = NULL;
#elif LWHEAP_USER_TRACE_DATA_TYPE == 2
    heap->freeBlockListHeader.__func = NULL;
    heap->freeBlockListHeader.__line = 0;
    heap->usedBlockListHeader.__func = NULL;
    heap->usedBlockListHeader.__line = 0;
#endif //LWHEAP_USER_TRACE_DATA_TYPE
    heap->usedBlockListHeader.next = NULL;
    heap->usedBlockListHeader.size = 0;
#if LWHEAP_MEMORY_TRACE_LEVEL == 2
    heap->freeBlockListHeader.__prev = NULL;
    heap->usedBlockListHeader.__prev = NULL;
#endif //LWHEAP_MEMORY_TRACE_LEVEL
    heap->freeBlockListHeader.__next = NULL;
    heap->usedBlockListHeader.__next = NULL;
#endif //LWHEAP_MEMORY_TRACE_LEVEL
}

__LWHEAP_WEAK void LwHeap_Lock(LwHeap_t* heap)
{
    (void)heap;
}

__LWHEAP_WEAK void LwHeap_Unlock(LwHeap_t* heap)
{
    (void)heap;
}

bool LwHeap_AddMem(LwHeap_t* heap, void* mptr, LwHeap_Size_t mlen)
{
    //判断给定的内存地址以及数据长度是否合法
    if(heap && mptr && mlen >= sizeof(LwHeap_Block_t)){

        //计算给定地址对齐到4字节需要丢弃的前端字节数
        int mdis = 0x4 - ((uint32_t)mptr & 0x3);

        //不为4表示需要丢弃, 为4表示已经对齐到4字节
        if(mdis != 4){

            //移动地址, 丢弃掉未对齐字节
            *(uint32_t*)(&mptr) += mdis;

            //长度减去丢弃掉的字节
            mlen -= mdis;
        }

        //判断丢弃了未对齐字节后, 剩余长度是否合法
        if(mlen >= sizeof(LwHeap_Block_t)){

            //将内存地址转换为内存块结构
            LwHeap_Block_t* block = __LWHEAP_BLOCK(mptr);

            //丢弃末尾未对齐内存
            block->size = mlen & (~0x3);

#if LWHEAP_ENABLE_MEMEORY_USE_RECORD != 0
            //记录内存大小
            heap->memCount.total += block->size;
            heap->memCount.free += block->size;
            heap->memCount.minval += block->size;
#endif

            //插入内存块
            /*------------------------------------------*/
            LwHeap_Lock(heap);
            /*------------------------------------------*/
            {
                //前一个block
                LwHeap_Block_t* prevBlock = &heap->freeBlockListHeader;

                //当前block
                LwHeap_Block_t* currBlock = prevBlock->next;

                //循环查找插入点: 地址升序排列
                while(currBlock != NULL){

                    //判断是否为插入点
                    if(block < currBlock){
                        break;
                    }

                    //转到下一个block
                    prevBlock = currBlock;
                    currBlock = currBlock->next;
                }

                //执行插入
                block->next     = currBlock;
                prevBlock->next = block;
            }
            /*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
            LwHeap_Unlock(heap);
            /*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/

            return true;
        }
    }
    return false;
}

#if LWHEAP_MEMORY_TRACE_LEVEL != 0
#if LWHEAP_USER_TRACE_DATA_TYPE == 0
void* LwHeap_Malloc(LwHeap_t* heap, LwHeap_Size_t reqsize, int align, const void* udat, LwHeap_Size_t usiz)
#elif LWHEAP_USER_TRACE_DATA_TYPE == 1
void* LwHeap_Malloc(LwHeap_t *heap, LwHeap_Size_t reqsize, int align, const char *ustr)
#elif LWHEAP_USER_TRACE_DATA_TYPE == 2
void* LwHeap_Malloc(LwHeap_t *heap, LwHeap_Size_t reqsize, int align, const char* func, uint32_t line)
#endif //LWHEAP_USER_TRACE_DATA_TYPE
#else
void* LwHeap_Malloc(LwHeap_t* heap, LwHeap_Size_t reqsize, int align)
#endif //LWHEAP_MEMORY_TRACE_LEVEL
{
    //申请内存为0, 直接返回NULL
    if(heap == NULL || reqsize == 0){
        return NULL;
    }

    //强制对齐到4字节
    if(align < 2) align = 2;

    //求取对齐到的字节数
    uint32_t alignByte = 1ul << align;

    //对齐判断MASK
    uint32_t alignMask = ~(0xFFFFFFFFul << align);

    //计算请求的内存大小, 加入头, 并将大小对齐到4字节
    reqsize += sizeof(LwHeap_Block_t) - sizeof(LwHeap_Block_t*);
    if(reqsize & 0x3){
        reqsize += 0x4 - (reqsize & 0x3);
    }

    void* rptr = NULL;

    /*------------------------------------------*/
    LwHeap_Lock(heap);
    /*------------------------------------------*/

    //上一个block
    LwHeap_Block_t* prevBlock = &heap->freeBlockListHeader;

    //当前block
    LwHeap_Block_t* currBlock = prevBlock->next;

    //循环查找可用的内存块
    while(currBlock != NULL){

        //初步判断内存块大小是否满足要求
        if(currBlock->size >= reqsize){

            //初始化分配block为当前block
            LwHeap_Block_t* allocBlock = currBlock;

            //用户可用地址与对齐mask相与
            uint32_t dis = ((uint32_t)__LWHEAP_BLOCK_TO_UBPTR(allocBlock)) & alignMask;

            //标记是否找到满足要求的内存块
            bool found = true;

            //地址未对齐
            if(dis != 0){

                //求取对齐须要的偏移
                dis = alignByte - dis;

                //进行地址偏移必须大于block头, 以便于进行分割
                while(dis < sizeof(LwHeap_Block_t)){
                    dis += alignByte;
                }

                //进行对齐操作后内存块仍然满足要求
                if(currBlock->size > dis && currBlock->size - dis >= reqsize){

                    //求取分配block的地址
                    allocBlock = (LwHeap_Block_t*)(((uint32_t)allocBlock) + dis);
                }
                else{

                    //内存块不满足要求
                    found = false;
                }
            }

            //找到了满足要求的内存块
            if(found == true){

                //保存下一个block的地址
                LwHeap_Block_t* nextBlock = currBlock->next;

                //找到的可用内存并非当前内存块首地址
                if(allocBlock != currBlock){

                    //切分内存块头计算出大小
                    uint32_t tempSize = ((uint32_t)allocBlock) - ((uint32_t)currBlock);

                    //计算切分后剩余的大小
                    allocBlock->size = currBlock->size - tempSize;

                    //记录切分出的大小
                    currBlock->size = tempSize;

                    //重置前一个block地址
                    prevBlock = currBlock;
                }

                //分配出内存较大, 还可以再切分
                if(allocBlock->size >= reqsize + sizeof(LwHeap_Block_t)){

                    //从尾部切分出一个块
                    currBlock = (LwHeap_Block_t*)(((uint32_t)allocBlock) + reqsize);

                    //计算切分出的大小
                    currBlock->size = allocBlock->size - reqsize;

                    //设置申请内存的大小
                    allocBlock->size = reqsize;

                    //连接空闲内存块
                    prevBlock->next = currBlock;
                    currBlock->next = nextBlock;
                }
                else{
                    //连接空闲内存块
                    prevBlock->next = nextBlock;
                }

#if LWHEAP_ENABLE_MEMEORY_USE_RECORD != 0
                //减掉分配的内存大小
                heap->memCount.free -= allocBlock->size;
                if(heap->memCount.minval > heap->memCount.free){
                    heap->memCount.minval = heap->memCount.free;
                }
#endif

                //标记被分配了
                allocBlock->size |= __LWHEAP_ALLOCATED_MASK;

//******************************************************************************
#if LWHEAP_MEMORY_TRACE_LEVEL != 0

                /*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
                LwHeap_Unlock(heap);
                /*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
#if LWHEAP_USER_TRACE_DATA_TYPE == 0
                //用户数据不为NULL, 申请内存并保存用户数据
                if(udat != NULL && ((uint32_t)udat) < __LWHEAP_DATA_FLAG_MIN_VALUE && usiz > 0){

                    //申请用户追踪数据内存空间
                    allocBlock->__data = lwheap_malloc(heap, usiz, 2, (const void*)__LWHEAP_DATA_FLAG_USER_TRACE, 0);

                    //申请成功则将用户数据copy过来
                    if(allocBlock->__data){
                        memcpy(allocBlock->__data, udat, usiz);
                        allocBlock->__dlen = usiz;
                    }
                    else{
                        //0xFFFFFFFE表示用户追踪数据内存空间申请失败
                        allocBlock->__data = (void*)__LWHEAP_DATA_FLAG_MALLOC_FAILED;
                        allocBlock->__dlen = 0;
                    }
                }
                else{
                    allocBlock->__data = (void*)udat;
                    allocBlock->__dlen = 0;
                }
#elif LWHEAP_USER_TRACE_DATA_TYPE == 1
                if(ustr != NULL && ((uint32_t)ustr) < __LWHEAP_DATA_FLAG_MIN_VALUE){
                    int slen = strlen(ustr) + 1;
                    allocBlock->__ustr = lwheap_malloc(heap, slen, 2, (void*)__LWHEAP_DATA_FLAG_USER_TRACE);
                    if(allocBlock->__ustr){
                        memcpy(allocBlock->__ustr, ustr, slen);
                    }
                    else{
                        allocBlock->__ustr = (void*)__LWHEAP_DATA_FLAG_MALLOC_FAILED;
                    }
                }
                else{
                    allocBlock->__ustr = NULL;
                }
#elif LWHEAP_USER_TRACE_DATA_TYPE == 2
                if(func != NULL && ((uint32_t)func) < __LWHEAP_DATA_FLAG_MIN_VALUE){
                    int slen = strlen(func) + 1;
                    allocBlock->__func = LwHeap_Malloc(heap, slen, 2, (void*)__LWHEAP_DATA_FLAG_USER_TRACE, 0);
                    if(allocBlock->__func){
                        memcpy(allocBlock->__func, func, slen);
                    }
                    else{
                        allocBlock->__func = (void*)__LWHEAP_DATA_FLAG_MALLOC_FAILED;
                    }
                }
                else{
                    allocBlock->__func = (char*)func;
                }
                allocBlock->__line = line;
#endif //LWHEAP_USER_TRACE_DATA_TYPE

                /*------------------------------------------*/
                LwHeap_Lock(heap);
                /*------------------------------------------*/

                //插入到使用链表中
                LwHeap_Block_t *__nextBlock = heap->usedBlockListHeader.__next;
                heap->usedBlockListHeader.__next = allocBlock;
                allocBlock->__next = __nextBlock;
#if LWHEAP_MEMORY_TRACE_LEVEL == 2
                allocBlock->__prev = &heap->usedBlockListHeader;
                if(__nextBlock != NULL){
                    __nextBlock->__prev = allocBlock;
                }
#endif
#endif
//******************************************************************************

                rptr = __LWHEAP_BLOCK_TO_UBPTR(allocBlock);
                break;
            }
        }

        //转到下一个block
        prevBlock = currBlock;
        currBlock = currBlock->next;
    }

    /*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
    LwHeap_Unlock(heap);
    /*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/

    return rptr;
}

#if LWHEAP_MEMORY_TRACE_LEVEL != 0
#if LWHEAP_USER_TRACE_DATA_TYPE == 0
void* LwHeap_Realloc(LwHeap_t* heap, void* mptr, LwHeap_Size_t newsize, int align, const void* udat, LwHeap_Size_t usiz)
#elif LWHEAP_USER_TRACE_DATA_TYPE == 1
void* LwHeap_Realloc(LwHeap_t* heap, void* mptr, LwHeap_Size_t newsize, int align, const char *ustr)
#elif LWHEAP_USER_TRACE_DATA_TYPE == 2
void* LwHeap_Realloc(LwHeap_t* heap, void* mptr, LwHeap_Size_t newsize, int align, const char* func, uint32_t line)
#endif //LWHEAP_USER_TRACE_DATA_TYPE
#else
void* LwHeap_Realloc(LwHeap_t* heap, void* mptr, LwHeap_Size_t newsize, int align)
#endif
{
    if(heap == NULL){
        return NULL;
    }

    //内存要求为0, 表示释放内存
    if(newsize == 0){
        LwHeap_Free(heap, mptr);
        return NULL;
    }

    if(mptr == NULL){
#if LWHEAP_MEMORY_TRACE_LEVEL != 0
#if LWHEAP_USER_TRACE_DATA_TYPE == 0
        return lwheap_malloc(heap, newsize, align, udat, usiz);
#elif LWHEAP_USER_TRACE_DATA_TYPE == 1
        return lwheap_malloc(heap, newsize, align, ustr);
#elif LWHEAP_USER_TRACE_DATA_TYPE == 2
        return LwHeap_Malloc(heap, newsize, align, func, line);
#endif
#else
        return lwheap_malloc(heap, newsize, align);
#endif
    }

    //计算请求的内存大小, 加入头, 并将大小对齐到4字节
    LwHeap_Size_t nsize = newsize + sizeof(LwHeap_Block_t) - sizeof(LwHeap_Block_t*);
    if(nsize & 0x3){
        nsize += 0x4 - (nsize & 0x3);
    }

    //是否需要重新malloc
    bool new_malloc = false;

    //获取block指针
    LwHeap_Block_t* block = __LWHEAP_UBPTR_TO_BLOCK(mptr);

    //新内存尺寸不超过原尺寸
    if(block->size >= nsize){

        //原尺寸可切割
        if(block->size >= nsize + sizeof(LwHeap_Block_t)){

            /*------------------------------------------*/
            LwHeap_Lock(heap);
            /*------------------------------------------*/

            //前一个块
            LwHeap_Block_t* prevBlock = &heap->freeBlockListHeader;

            //当前块
            LwHeap_Block_t* currBlock = prevBlock->next;

            //循环查找块的原始位置
            while(currBlock != NULL){
                if(block < currBlock){
                    break;
                }
                prevBlock = currBlock;
                currBlock = currBlock->next;
            }

            //保存下一个block的地址
            LwHeap_Block_t* nextBlock = currBlock->next;

            //从尾部切分出一个块
            currBlock = (LwHeap_Block_t*)(((uint32_t)block) + nsize);

            //计算切分出的大小
            currBlock->size = block->size - nsize;

#if LWHEAP_ENABLE_MEMEORY_USE_RECORD != 0
            //增加空闲内存
            heap->memCount.free += currBlock->size;
#endif

            //设置申请内存的大小
            block->size = nsize;

            //连接空闲内存块
            prevBlock->next = currBlock;
            currBlock->next = nextBlock;

            /*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
            LwHeap_Unlock(heap);
            /*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
        }
    }
    //新尺寸比原尺寸大
    else{

        /*------------------------------------------*/
        LwHeap_Lock(heap);
        /*------------------------------------------*/

        //前一个块
        LwHeap_Block_t* prevBlock = &heap->freeBlockListHeader;

        //当前块
        LwHeap_Block_t* currBlock = prevBlock->next;

        //循环查找块的原始位置
        while(currBlock != NULL){
            if(block < currBlock){
                break;
            }
            prevBlock = currBlock;
            currBlock = currBlock->next;
        }

        //block与currBlock内存地址连续
        if(((uint32_t)block) + block->size == ((uint32_t)currBlock)){

            //计算连续总大小
            uint32_t xsize = block->size + currBlock->size;

            //大小满足要求
            if(xsize >= nsize){

                //总大小可再切割
                if(xsize >= nsize + sizeof(LwHeap_Block_t)){

                    //保存下一个block的地址
                    LwHeap_Block_t* nextBlock = currBlock->next;

                    //从尾部切分出一个块
                    currBlock = (LwHeap_Block_t*)(((uint32_t)block) + nsize);

                    //计算切分出的大小
                    currBlock->size = xsize - nsize;

#if LWHEAP_ENABLE_MEMEORY_USE_RECORD != 0
                    //重新计算空闲内存大小
                    heap->memCount.free -= nsize - block->size;
                    if(heap->memCount.minval > heap->memCount.free){
                        heap->memCount.minval = heap->memCount.free;
                    }
#endif

                    //设置申请内存的大小
                    block->size = nsize;

                    //连接空闲内存块
                    prevBlock->next = currBlock;
                    currBlock->next = nextBlock;
                }
                else{
#if LWHEAP_ENABLE_MEMEORY_USE_RECORD != 0
                    //重新计算空闲内存大小
                    heap->memCount.free -= currBlock->size;
                    if(heap->memCount.minval > heap->memCount.free){
                        heap->memCount.minval = heap->memCount.free;
                    }
#endif
                    //不可再切割,直接拼接内存
                    block->size = xsize;
                    prevBlock->next = currBlock->next;
                }
            }
            else{
                new_malloc = true;
            }
        }
        else{
            new_malloc = true;
        }

        /*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
        LwHeap_Unlock(heap);
        /*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
    }

    //需要重新分配内存
    if(new_malloc == true){

        //分配新内存
#if LWHEAP_MEMORY_TRACE_LEVEL != 0
#if LWHEAP_USER_TRACE_DATA_TYPE == 0
        mptr = lwheap_malloc(heap, newsize, align, NULL, 0);
#elif LWHEAP_USER_TRACE_DATA_TYPE == 1
        mptr = lwheap_malloc(heap, newsize, align, NULL);
#elif LWHEAP_USER_TRACE_DATA_TYPE == 2
        mptr = LwHeap_Malloc(heap, newsize, align, NULL, 0);
#endif //LWHEAP_USER_TRACE_DATA_TYPE
#else
        mptr = lwheap_malloc(heap, newsize, align);
#endif //LWHEAP_MEMORY_TRACE_LEVEL
        //分配成功
        if(mptr){
#if LWHEAP_MEMORY_TRACE_LEVEL != 0

            //获得block
            LwHeap_Block_t* newBlock = __LWHEAP_UBPTR_TO_BLOCK(mptr);
#if LWHEAP_USER_TRACE_DATA_TYPE == 0

            //直接将用户数据搬过来
            newBlock->__data = block->__data;
            newBlock->__dlen = block->__dlen;

            //直接置空
            block->__data = NULL;
            block->__dlen = 0;
#elif LWHEAP_USER_TRACE_DATA_TYPE == 1
            newBlock->__ustr = block->__ustr;
            block->__ustr = NULL;
#elif LWHEAP_USER_TRACE_DATA_TYPE == 2
            newBlock->__func = block->__func;
            newBlock->__line = block->__line;
#endif //LWHEAP_USER_TRACE_DATA_TYPE
#endif //LWHEAP_MEMORY_TRACE_LEVEL
            //搬移原内存中的数据
            memcpy(mptr, __LWHEAP_BLOCK_TO_UBPTR(block), block->size - (sizeof(LwHeap_Block_t) - sizeof(LwHeap_Block_t*)));

            //销毁原内存
            LwHeap_Free(heap, __LWHEAP_BLOCK_TO_UBPTR(block));
        }
    }
//******************************************************************************
#if LWHEAP_MEMORY_TRACE_LEVEL != 0
#if LWHEAP_USER_TRACE_DATA_TYPE == 0
    if(((uint32_t)udat) < __LWHEAP_DATA_FLAG_MIN_VALUE){

        //注销用户数据内存
        if(block->__data != NULL && ((uint32_t)block->__data) < __LWHEAP_DATA_FLAG_MIN_VALUE){
            LwHeap_Free(heap, block->__data);
        }

        //重新分配内存
        if(udat != NULL && usiz){
            block->__data = lwheap_malloc(heap, usiz, 2, (const void*)__LWHEAP_DATA_FLAG_USER_TRACE, 0);
            if(block->__data){

                //写入数据
                memcpy(block->__data, udat, usiz);
                block->__dlen = usiz;
            }
            else{
                block->__data = (void*)__LWHEAP_DATA_FLAG_MALLOC_FAILED;
                block->__dlen = 0;
            }
        }
        else{
            block->__data = NULL;
            block->__dlen = 0;
        }
    }
#elif LWHEAP_USER_TRACE_DATA_TYPE == 1
    if(((uint32_t)ustr) < __LWHEAP_DATA_FLAG_MIN_VALUE){
        //注销用户数据内存
        if(block->__ustr != NULL && ((uint32_t)block->__ustr) < __LWHEAP_DATA_FLAG_MIN_VALUE){
            LwHeap_Free(heap, block->__ustr);
        }

        //重新分配内存
        if(ustr != NULL){

            int slen = strlen(ustr) + 1;
            block->__ustr = lwheap_malloc(heap, slen, 2, (const void*)__LWHEAP_DATA_FLAG_USER_TRACE);
            if(block->__ustr){

                //写入数据
                memcpy(block->__ustr, ustr, slen);
            }
            else{
                block->__ustr = (void*)__LWHEAP_DATA_FLAG_MALLOC_FAILED;
            }
        }
        else{
            block->__ustr = NULL;
        }
    }
#elif LWHEAP_USER_TRACE_DATA_TYPE == 2
    if(((uint32_t)func) < __LWHEAP_DATA_FLAG_MIN_VALUE){
        //注销用户数据内存
        if(block->__func != NULL && ((uint32_t)block->__func) < __LWHEAP_DATA_FLAG_MIN_VALUE){
            LwHeap_Free(heap, block->__func);
        }

        //重新分配内存
        if(func != NULL){

            int slen = strlen(func) + 1;
            block->__func = lwheap_malloc(heap, slen, 2);
            if(block->__func){

                //写入数据
                memcpy(block->__func, func, slen);
            }
            else{
                block->__func = (void*)__LWHEAP_DATA_FLAG_MALLOC_FAILED;
            }
        }
        else{
            block->__func = NULL;
        }
    }
    block->__line = line;
#endif //LWHEAP_USER_TRACE_DATA_TYPE
#endif //LWHEAP_MEMORY_TRACE_LEVEL
//******************************************************************************
    return mptr;
}

bool LwHeap_Free(LwHeap_t* heap, void* mptr)
{
    if(heap == NULL || mptr == NULL){
        return false;
    }

    //获取block指针
    LwHeap_Block_t* block = __LWHEAP_UBPTR_TO_BLOCK(mptr);

    //检查是否为分配的内存
    if(block->size & __LWHEAP_ALLOCATED_MASK){

        //取消分配标志
        block->size &= ~__LWHEAP_ALLOCATED_MASK;

//******************************************************************************
#if LWHEAP_MEMORY_TRACE_LEVEL != 0
        {
#if LWHEAP_MEMORY_TRACE_LEVEL == 2

            //释放用户追踪数据用内存空间
#if LWHEAP_USER_TRACE_DATA_TYPE == 0
            if(block->__data != NULL && ((uint32_t)block->__data) < __LWHEAP_DATA_FLAG_MIN_VALUE){
                if(LwHeap_Free(heap, block->__data) == false){
                    return false;
                }
                block->__data = NULL;
            }
#elif LWHEAP_USER_TRACE_DATA_TYPE == 1
            if(block->__ustr != NULL && ((uint32_t)block->__ustr) < __LWHEAP_DATA_FLAG_MIN_VALUE){
                if(LwHeap_Free(heap, block->__ustr) == false){
                    return false;
                }
                block->__ustr = NULL;
            }
#elif LWHEAP_USER_TRACE_DATA_TYPE == 2
            if(block->__func != NULL && ((uint32_t)block->__func) < __LWHEAP_DATA_FLAG_MIN_VALUE){
                if(LwHeap_Free(heap, block->__func) == false){
                    return false;
                }
                block->__func = NULL;
            }
#endif //LWHEAP_USER_TRACE_DATA_TYPE

            /*------------------------------------------*/
            LwHeap_Lock(heap);
            /*------------------------------------------*/

            //取出前后used block
            LwHeap_Block_t* __prevBlock = block->__prev;
            LwHeap_Block_t* __nextBlock = block->__next;

            //连接前后block
            if(__prevBlock == NULL){
                /*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
                LwHeap_Unlock(heap);
                /*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
                return false;
            }
            __prevBlock->__next = __nextBlock;
            if(__nextBlock != NULL){
                __nextBlock->__prev = __prevBlock;
            }
            /*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
            LwHeap_Unlock(heap);
            /*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
#else
            /*------------------------------------------*/
            LwHeap_Lock(heap);
            /*------------------------------------------*/

            //取出used block
            LwHeap_Block_t* __prevBlock = &heap->usedBlockListHeader;
            LwHeap_Block_t* __currBlock = __prevBlock->__next;

            //循环查找内存块位置
            while(__currBlock != NULL){
                if(__currBlock == block){
                    break;
                }
                __prevBlock = __currBlock;
                __currBlock = __currBlock->__next;
            }

            if(__currBlock == NULL){
                /*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
                LwHeap_Unlock(heap);
                /*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
                return false;
            }

            //连接前后block
            __prevBlock->__next = __currBlock->__next;

            /*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
            LwHeap_Unlock(heap);
            /*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
#if LWHEAP_USER_TRACE_DATA_TYPE == 0
            //释放用户追踪数据用内存空间
            if(block->__data != NULL && ((uint32_t)block->__data) < __LWHEAP_DATA_FLAG_MIN_VALUE){
                if(LwHeap_Free(heap, block->__data) == false){
                    return false;
                }
                block->__data = NULL;
            }
#elif LWHEAP_USER_TRACE_DATA_TYPE == 1
            if(block->__ustr != NULL && ((uint32_t)block->__ustr) < __LWHEAP_DATA_FLAG_MIN_VALUE){
                if(LwHeap_Free(heap, block->__ustr) == false){
                    return false;
                }
                block->__ustr = NULL;
            }
#elif LWHEAP_USER_TRACE_DATA_TYPE == 2
            if(block->__func != NULL && ((uint32_t)block->__func) < __LWHEAP_DATA_FLAG_MIN_VALUE){
                if(LwHeap_Free(heap, block->__func) == false){
                    return false;
                }
                block->__func = NULL;
            }
#endif //LWHEAP_USER_TRACE_DATA_TYPE
#endif
        }
#endif
//******************************************************************************

        /*------------------------------------------*/
        LwHeap_Lock(heap);
        /*------------------------------------------*/

        //前一个块
        LwHeap_Block_t* prevBlock = &heap->freeBlockListHeader;

        //当前块
        LwHeap_Block_t* currBlock = prevBlock->next;

        //循环查找插入点
        while(currBlock != NULL){
            if(block < currBlock){
                break;
            }
            prevBlock = currBlock;
            currBlock = currBlock->next;
        }

#if LWHEAP_ENABLE_MEMEORY_USE_RECORD != 0
        //恢复空闲内存
        heap->memCount.free += block->size;
#endif

        //前块合并
        if(prevBlock != (&heap->freeBlockListHeader) && ((uint32_t)prevBlock) + prevBlock->size == ((uint32_t)block)){
            prevBlock->size += block->size;
            block = prevBlock;
        }
        else{
            prevBlock->next = block;
        }

        //后块合并
        if(currBlock && ((uint32_t)block) + block->size == ((uint32_t)currBlock)){
            block->size += currBlock->size;
            block->next = currBlock->next;
        }
        else{
            block->next = currBlock;
        }

        /*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
        LwHeap_Unlock(heap);
        /*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/

        return true;
    }
    return false;
}

/******************************************************************************/
#if LWHEAP_MEMORY_TRACE_LEVEL != 0 && LWHEAP_USER_TRACE_DATA_TYPE != 0
static const char __LwHeap_ConstStr_Trace[] = "LwHeap_Trace";
static const char __LwHeap_ConstStr_Inner[] = "LwHeap_Inner";
static const char __LwHeap_ConstStr_Error[] = "LwHeap_Error";
#endif
/******************************************************************************/

LwHeap_Iterator_t* LwHeap_IteratorBegin(LwHeap_t* heap, uint32_t flag)
{
#if LWHEAP_MEMORY_TRACE_LEVEL == 0
    LwHeap_Iterator_t* iterator = lwheap_malloc(heap, sizeof(LwHeap_Iterator_t), 2);
    (void)flag;
#else
#if LWHEAP_USER_TRACE_DATA_TYPE == 0
    LwHeap_Iterator_t* iterator = lwheap_malloc(heap, sizeof(LwHeap_Iterator_t), 2, (const void*)__LWHEAP_DATA_FLAG_INNER_USE, 0);
#elif LWHEAP_USER_TRACE_DATA_TYPE == 1
    LwHeap_Iterator_t* iterator = lwheap_malloc(heap, sizeof(LwHeap_Iterator_t), 2, (const char*)__LWHEAP_DATA_FLAG_INNER_USE);
#elif LWHEAP_USER_TRACE_DATA_TYPE == 2
    LwHeap_Iterator_t* iterator = lwheap_malloc(heap, sizeof(LwHeap_Iterator_t), 2);
#endif
#endif
    if(iterator){
        iterator->heap = heap;
        LwHeap_Lock(iterator->heap);
#if LWHEAP_MEMORY_TRACE_LEVEL == 0
        iterator->flags = LWHEAP_ITERATOR_FLAG_FREE_LIST;
        iterator->prevBlock = &heap->freeBlockListHeader;
        iterator->currBlock = iterator->prevBlock->next;
#else
        iterator->flags = flag;
        if(flag == LWHEAP_ITERATOR_FLAG_FREE_LIST){
            iterator->prevBlock = &heap->freeBlockListHeader;
            iterator->currBlock = iterator->prevBlock->next;
        }
        else{
            iterator->prevBlock = &heap->usedBlockListHeader;
            iterator->currBlock = iterator->prevBlock->__next;
        }
#endif
    }
    return iterator;
}

bool LwHeap_IteratorRead(LwHeap_Iterator_t* iterator, LwHeap_IteratorData_t* pdata)
{
    if(iterator->currBlock){
        pdata->blockAddr = iterator->currBlock;
        pdata->blockSize = iterator->currBlock->size & (~__LWHEAP_ALLOCATED_MASK);
#if LWHEAP_MEMORY_TRACE_LEVEL == 0
        pdata->type.free.nextBlock = iterator->currBlock->next;
        pdata->type.free.userPointer = __LWHEAP_BLOCK_TO_UBPTR(iterator->currBlock);
#else
        if(iterator->flags == LWHEAP_ITERATOR_FLAG_FREE_LIST){
            pdata->type.free.nextBlock = iterator->currBlock->next;
            pdata->type.free.userPointer = __LWHEAP_BLOCK_TO_UBPTR(iterator->currBlock);
        }
        else{
#if LWHEAP_MEMORY_TRACE_LEVEL == 2
            pdata->type.used.prevBlock = iterator->currBlock->__prev;
#endif
            pdata->type.used.nextBlock = iterator->currBlock->__next;
            pdata->type.used.userPointer = __LWHEAP_BLOCK_TO_UBPTR(iterator->currBlock);
#if LWHEAP_USER_TRACE_DATA_TYPE == 0
            pdata->type.used.data = ((uint32_t)iterator->currBlock->__data) < __LWHEAP_DATA_FLAG_MIN_VALUE ? iterator->currBlock->__data : NULL;
            pdata->type.used.dlen = iterator->currBlock->__dlen;
#elif LWHEAP_USER_TRACE_DATA_TYPE == 1
            if((uint32_t)iterator->currBlock->__ustr < __LWHEAP_DATA_FLAG_MIN_VALUE){
                pdata->type.used.func = iterator->currBlock->__ustr;
            }
            else switch ((uint32_t)iterator->currBlock->__ustr) {
            case __LWHEAP_DATA_FLAG_INNER_USE:
                pdata->type.used.ustr = __LwHeap_ConstStr_Inner;
                break;
            case __LWHEAP_DATA_FLAG_USER_TRACE:
                pdata->type.used.ustr = __LwHeap_ConstStr_Trace;
                break;
            default:
                pdata->type.used.ustr = __LwHeap_ConstStr_Error;
                break;
            }
#elif LWHEAP_USER_TRACE_DATA_TYPE == 2
            if((uint32_t)iterator->currBlock->__func < __LWHEAP_DATA_FLAG_MIN_VALUE){
                pdata->type.used.func = iterator->currBlock->__func;
            }
            else switch ((uint32_t)iterator->currBlock->__func) {
            case __LWHEAP_DATA_FLAG_INNER_USE:
                pdata->type.used.func = __LwHeap_ConstStr_Inner;
                break;
            case __LWHEAP_DATA_FLAG_USER_TRACE:
                pdata->type.used.func = __LwHeap_ConstStr_Trace;
                break;
            default:
                pdata->type.used.func = __LwHeap_ConstStr_Error;
                break;
            }
            pdata->type.used.line = iterator->currBlock->__line;
#endif
        }
#endif

        iterator->prevBlock = iterator->currBlock;
#if LWHEAP_MEMORY_TRACE_LEVEL == 0
        iterator->currBlock = iterator->currBlock->next;
#else
        if(iterator->flags == LWHEAP_ITERATOR_FLAG_FREE_LIST){
            iterator->currBlock = iterator->currBlock->next;
        }
        else{
            iterator->currBlock = iterator->currBlock->__next;
        }
#endif
        return true;
    }
    return false;
}

void LwHeap_IteratorEnd(LwHeap_Iterator_t* iterator)
{
    LwHeap_Unlock(iterator->heap);
    LwHeap_Free(iterator->heap, iterator);
}
